public class LongestPalindromicSubstring {
    public String longestPalindrome(String s) {
        char[] ch = s.toCharArray();
        int len = 0;
        int begin = 0, end = 0; // 作为记录回文子串的左右区间指针
        // i 作为中心点
        int n = s.length();
        for (int i = 0; i < n; i++) {
            int left = i, right = i;
            while (right + 1 < n && ch[right + 1] == ch[left]) {
                right++;
            }
            while (left - 1 >= 0 && ch[left - 1] == ch[right]) {
                left--;
            }
            // [left, right] 区域内都是相同的字符, 也属于回文子串
            // 记录当前回文子串的长度和下标
            if (right - left + 1 > len) {
                len = right - left + 1;
                begin = left;
                end = right;
            }

            while (left - 1 >= 0 && right + 1 < n && ch[left - 1] == ch[right + 1]) {
                // 找与中心点 i 不同元素的回文子串
                // 假如所给字符串是  c abbba d, 上面走完后 left指向最左边的 b, right 指向最右边的 b
                // 接下来就是把 最左边的 a 和最右边的 a 扩展进来
                left--;
                right++;
                if (right - left + 1 > len) {
                    len = right - left + 1;
                    begin = left;
                    end = right;
                }
            }
            // 记录回文子串的长度和下标两个 if 语句是必要的, 也不能合在一起
        }
        return s.substring(begin, end + 1);
    }

}
